package com.hanxiaozhang.no10leetcode.tree;

/**
 * 〈一句话功能简述〉<br>
 * 〈给一个元素以升序排列的数组，将其转化为一棵平衡二叉搜索树〉
 * <p>
 * 平衡二叉树的定义为一棵树左右子树的节点高度差不大于1。
 * 实例1：
 * .        0
 * .      /   \
 * .    -3     9
 * .    /    /
 * . -10    5
 * 输入：nums = [-10,-3,0,5,9]
 * 输出：[0,-3,9,-10,null,5]
 * .      0
 * .    /   \
 * .  -10    5
 * .     \     \
 * .     -3     9
 * 解释：[0,-10,5,null,-3,null,9]也将被视为正确答案
 * <p>
 * 实例2：
 * 输入：nums = [1,3]
 * 输出：[3,1]
 * 解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
 * <p>
 * 思路：
 * 采用递归，通过(start+end+1)/2快速获取到对应的中间index ，
 * 然后递归执行，其左子树为递归左边半个数组，右子树递归右边半个数组。
 *
 * @author hanxinghua
 * @create 2024/4/11
 * @since 1.0.0
 */
public class No108ConvertSortedArrayToBST {

    public static void main(String[] args) {
        int[] nums = {-10, -3, 0, 5, 9};

        TreeNode tree = method1(nums);

        System.out.println();

    }


    /**
     * 方法1
     * 思路：
     * 采用递归，通过(start+end+1)/2快速获取到对应的中间index ，
     * 然后递归执行，其左子树为递归左边半个数组，右子树递归右边半个数组。
     *
     * @param nums
     * @return
     */
    public static TreeNode method1(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }

        return recursion(nums, 0, nums.length - 1);
    }


    /**
     * 递归
     *
     * @param nums
     * @param start 开始位置
     * @param end   结束位置
     * @return
     */
    private static TreeNode recursion(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }

        int mid = start + (end - start) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = recursion(nums, start, mid - 1);
        node.right = recursion(nums, mid + 1, end);
        return node;
    }

}
